home *** CD-ROM | disk | FTP | other *** search
/ SGI Developer Toolbox 6.1 / SGI Developer Toolbox 6.1 - Disc 4.iso / src / exampleCode / viewkit / xcontact / parody / btree.h < prev    next >
Encoding:
C/C++ Source or Header  |  1994-08-02  |  2.6 KB  |  96 lines
  1. // ------------- btree.h
  2.  
  3. #ifndef BTREE_H
  4. #define BTREE_H
  5.  
  6. #include <fstream.h>
  7. #include "linklist.h"
  8. #include "node.h"
  9.  
  10. class Key;
  11.  
  12. // -------- b-tree index file
  13. class Index : public FileHeader    {
  14. public:
  15.     Index(pString name) : FileHeader(name) {}
  16.     pBool NewFile() { return newfile; }
  17. };
  18.  
  19. class TNode;
  20.  
  21. // -------- b-tree header record
  22. struct TreeHeader {
  23.     NodeNbr rootnode;    // node number of the root
  24.     int keylength;         // length of a key in this b-tree
  25.     TreeHeader() { rootnode = keylength = 0; }
  26. };
  27.  
  28. // --------- b-tree index
  29. class Btree : public LinkedListEntry    {
  30.     TreeHeader header;    // btree header
  31.     NodeNbr currnode;        // current node number
  32.     TNode *trnode;            // -> current node value
  33.     Key *nullkey;            // for padding nodes and calling Make
  34.     Index& index;            // index file this tree lives in
  35.     long headeraddr;        // offset where header lives
  36. public:
  37.     Btree(Index& ndx, Key *ky);
  38.     ~Btree();
  39.     void Insert(void *keypointer);
  40.     void Delete(void *keypointer);
  41.     pBool Find(void *keypointer);
  42.     Key *Current();
  43.     Key *First();
  44.     Key *Last();
  45.     Key *Next();
  46.     Key *Previous();
  47.     void SetKeyLength(int kl) { header.keylength = kl; }
  48.     Index& IndexFile()        { return index; }
  49.     Key *NullKey()               { return nullkey; }
  50.     NodeNbr Root()               { return header.rootnode; }
  51.     NodeNbr KeyLength()           { return header.keylength; }
  52. };
  53.  
  54. // ------------- b-tree TNode class
  55. class TNode : public Node    {
  56.     friend Btree;
  57.     struct TNodeHeader    {
  58.         pBool isleaf;            // true if node is a leaf
  59.         NodeNbr parent;        // parent to this node
  60.         NodeNbr leftsibling;    // left sibling node
  61.         NodeNbr rightsibling;// right sibling node
  62.         int keycount;            // number of keys in this node
  63.         NodeNbr lowernode;    // lower node associated with
  64.                                     // keys < keys in this node
  65.         TNodeHeader()
  66.             { isleaf = pFalse; parent = leftsibling =
  67.                 rightsibling =    keycount = lowernode = 0; }
  68.     } header;
  69.     Key *currkey;                // current key
  70.     Btree *btree;                // btree that owns this node
  71.     LinkedListHead keys;        // the keys in this node
  72. public:
  73.     TNode(Btree *bt, NodeNbr node);
  74.     ~TNode();
  75.     pBool SearchNode(Key *keyvalue);
  76.     void Insert(Key *keyvalue);
  77.     int m();
  78.     void WriteKey(Key *thiskey);
  79.     void Adopt(NodeNbr node);
  80.     void Adoption();
  81.     pBool isLeaf()               { return header.isleaf; }
  82.     NodeNbr Parent()           { return header.parent; }
  83.     NodeNbr LeftSibling()  { return header.leftsibling; }
  84.     NodeNbr RightSibling() { return header.rightsibling; }
  85.     int KeyCount()           { return header.keycount; }
  86.     NodeNbr LowerNode()       { return header.lowernode; }
  87.     pBool Redistribute(NodeNbr sib);
  88.     pBool Implode(TNode &right);
  89.     int NodeHeaderSize()
  90.         { return sizeof(TNodeHeader)+Node::NodeHeaderSize(); }
  91.     TNode& operator=(TNode &tnode);
  92. };
  93.  
  94. #endif
  95.  
  96.